In commercial printing, printing speeds are in the thousands of pages-per-minute (ppm), typically measured in meters/second or monthly throughput. Such printing speeds are achieved using commodity hardware, and configuring software to have a suitable high level of parallelism.
Speeds of printing machines are increasing, as commodity hardware becomes cheaper and more powerful, customer demands increase, and processing becomes increasingly centralised on a global scale. Cloud-based services are an example of such trends. However, with improved hardware, deficiencies in scalability of existing software is exposed, and a need to adapt software and create new algorithms arises.
In the printing of a page, objects arrive in z-order, and are typically organised into y-dimension bands, where each band consists of one or more consecutive scan lines. Parallelism is therefore possible both in the z-dimension by processing objects as the objects arrive, and in the y-dimension by processing bands in parallel. Typically, y-dimension parallelism must wait for all objects to be received before proceeding. The obstacle to achieving y-dimension parallelism is due to dependencies between bands, caused by objects that span multiple bands on a page. If a band contains an object that starts at a scan line prior to a first scan line of the band, the object will typically need to be tracked until the state of the object at the start of the band is known, so that the band can be processed or rendered. Therefore, the band is dependent on the tracking information produced by the previous band. Tracking is a time-consuming process, typically involving the vectorising and possible scan conversion of edges if the object up to the scan line or band the object is being tracked to.
Some conventional rendering methods include expensive pre-processing of each object spanning multiple bands to form a collection of non-overlapping objects that each fit within a single predefined band. Other conventional rendering methods include merging of adjacent bands so that the merged band wholly contains objects, thereby avoiding the need to partition objects. Merging bands, however, reduces available parallelism.
Other conventional rendering methods simply re-track each object from an origin to the start of each band, for each band that the object intersects. Simply re-tracking each object can be prohibitively expensive for complex objects that intersect multiple bands, as portions of the objects need to be processed multiple times.
Thus a need exists for an improved rendering method.